package string;

public class ZhengZeBiaoDaShiPiPeiLcof {


  public static void main(String[] args) {

    String s = "aaaaaaaaaaaaab";
    String p = "a*a*a*a*a*a*a*a*a*a*c";
    Solution6 solution6 = new Solution6();
    System.out.println(solution6.isMatch(s, p));
//    System.out.println("".charAt(0));
  }

  /**
   * '.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）
   * aaa与a*匹配
   * aaa与a.a匹配
   * aaa与ab*ac*a匹配
   * ab与.*匹配
   * aaa与ab*a*c*a匹配
   */
  public static boolean isMatch(String s, String p) {
    if (s == null || p == null) {
      return false;
    }
    if ("".equals(s) && "".equals(p)) {
      return true;
    }

    char[] str = s.toCharArray();
    char[] pattern = p.toCharArray();
    int i, j;
    for (i = 0, j = 0; i < str.length && j < pattern.length; ++i) {
      if (str[i] != pattern[j] && pattern[j] != '.' && pattern[j] != '*') {
        //aaa与ab*ac*a,遇到不匹配比如a和b,得再看看它后面
        if ((j + 2) < pattern.length && pattern[j + 1] == '*' && pattern[j + 2] == str[i]) {
          j += 3;
          continue;
        } else {
          return false;
        }
      } else if (str[i] != pattern[j] && pattern[j] == '.') {
        ++j;
        continue;
      } else if (str[i] == pattern[j]) {
        ++j;
        continue;
      } else if (str[i] != pattern[j] && pattern[j] == '*') {
        if ((j - 1 >= 0) && (pattern[j - 1] == str[i] || pattern[j - 1] == '.')) {
          if ((str.length - 1 - i) > (pattern.length - 1 - j)) {
            continue;
          } else {
            ++j;
            continue;
          }
        }
      }
    }
    if (i >= str.length && j < pattern.length) {
      while (j < pattern.length) {
        if (pattern[j] == '*') {
          ++j;
        } else if ((j + 1) < pattern.length && pattern[j] != '*' && pattern[j + 1] == '*') {
          j += 2;
        }
      }
    }
    if (i >= str.length && j >= pattern.length) {
      return true;
    } else {
      return false;
    }
  }

  static class Solution1 {
    public boolean isMatch(String s, String p) {
      if (p.length() <= 0) return s.length() <= 0;
      boolean match = (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
      if (p.length() > 1 && p.charAt(1) == '*') {
        return isMatch(s, p.substring(2)) || (match && isMatch(s.substring(1), p));
      } else {
        return match && isMatch(s.substring(1), p.substring(1));
      }
    }
  }

  /**
   * 使用dp
   */
  class Solution2 {
    public boolean isMatch(String s, String p) {
      char[] sChars = s.toCharArray();
      char[] pChars = p.toCharArray();

      boolean[][] dp = new boolean[pChars.length + 1][sChars.length + 1];

      for (int i = 0; i <= pChars.length; ++i) {
        dp[i][0] = true;
      }

      for (int i = 1, j = 1; i <= pChars.length && j <= sChars.length; ++j) {
        if (i < pChars.length && pChars[i] == '*') {
          if (!isEquals(sChars[j - 1], pChars[i - 1])) {
            i += 2;
            --j;
          } else {
            dp[i][j] = dp[i - 1][j - 1];
            ++i;
          }
        } else {
          if (!isEquals(sChars[j - 1], pChars[i - 1])) {
            return false;
          }
        }
        if (isEquals(sChars[j - 1], pChars[i - 1])) {
          ++i;
          dp[i][j] = dp[i - 1][j - 1];
          continue;
        }

        if (pChars[i - 1] == '*') {
          int k = j;
          while (k <= sChars.length) {
            if (isEquals(sChars[j - 1], pChars[i - 1])) {
              dp[i][j] = dp[i - 1][j - 1];
              if (isEquals(sChars[k - 1], pChars[i - 1])) {
                dp[i][k] = true;
              }
            }
          }
        }
      }

      return false;
    }

    public boolean isEquals(char s, char p) {
      return s == p ? true : (p == '.' ? true : false);
    }
  }

  /**
   * 使用dp
   * https://s3.ax1x.com/2021/02/02/yuVb79.png
   */
  static class Solution3 {
    public boolean isMatch(String s, String p) {
      int m = s.length();
      int n = p.length();

      boolean[][] f = new boolean[m + 1][n + 1];
      f[0][0] = true;
      for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
          if (p.charAt(j - 1) == '*') {
            f[i][j] = f[i][j - 2];
            if (matches(s, p, i, j - 1)) {
              f[i][j] = f[i][j] || f[i - 1][j];
            }
          } else {
            if (matches(s, p, i, j)) {
              f[i][j] = f[i - 1][j - 1];
            }
          }
        }
      }
      return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
      if (i == 0) {
        return false;
      }
      if (p.charAt(j - 1) == '.') {
        return true;
      }
      return s.charAt(i - 1) == p.charAt(j - 1);
    }
  }

  class Solution4 {

    public boolean firstMatch(String s, String p, int i, int j) {
      return s.charAt(i) == p.charAt(j) || p.charAt(j) == '.';
    }

    public boolean isMatch(String s, String p) {
      boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];

      dp[0][0] = true;

      for (int j = 2; j <= p.length(); ++j) {
        dp[0][j] = (p.charAt(j - 1) == '*' && dp[0][j - 2]);
      }

      for (int i = 0; i < s.length(); ++i) {
        for (int j = 0; j < p.length(); ++j) {
          if (p.charAt(j) == '*') {
            dp[i + 1][j + 1] = dp[i + 1][j - 1] || firstMatch(s, p, i, j - 1) && dp[i][j + 1];
          } else {
            dp[i + 1][j + 1] = firstMatch(s, p, i, j) && dp[i][j];
          }
        }
      }
      return dp[s.length()][p.length()];
    }
  }

  /**
   * 使用递归
   */
  class Solution5 {
    public boolean isMatch(String s, String p) {
      if ("".equals(s) && "".equals(p)) return true;

      if (p.length() > 1 && p.charAt(1) == '*') {
        if (s.length() >= 1 && isEquals(s.charAt(0), p.charAt(0))) {
          //当遇到a*时可以将其作为0个a,1个a,多个a
          //1个a【isMatch(s.substring(1), p.substring(2))】,
          //多个a【isMatch(s.substring(1), p)】合并为【isMatch(s.substring(1), p)】
          //如果不将其合并，则会超时
          return isMatch(s, p.substring(2)) || isMatch(s.substring(1), p);
        } else {
          return isMatch(s, p.substring(2));
        }
      } else {
        if ((s.length() >= 1 && p.length() >= 1) && isEquals(s.charAt(0), p.charAt(0))) {
          return isMatch(s.substring(1), p.substring(1));
        } else {
          return false;
        }
      }
    }

    public boolean isEquals(char s, char p) {
      if (p == s) {
        return true;
      } else if (p == '.') {
        return true;
      } else {
        return false;
      }
    }
  }

  static class Solution6 {

    public boolean isMatch(String s, String p) {

      boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
      dp[0][0] = true;
      for (int j = 1; j <= p.length(); ++j) {
        if (p.charAt(j - 1) == '*') {
          dp[0][j] = dp[0][j - 2];
        }
      }

      for (int i = 1; i <= s.length(); ++i) {
        for (int j = 1; j <= p.length(); ++j) {
          if (isEquals(s.charAt(i - 1), p.charAt(j - 1))) {
            dp[i][j] = dp[i - 1][j - 1];
          }
          if (p.charAt(j - 1) == '*' && j > 1) {
            dp[i][j] =
                    dp[i][j - 2]
                    || (dp[i - 1][j - 1] && isEquals(s.charAt(i - 1), p.charAt(j - 2)))
                    ||(dp[i - 1][j] && isEquals(s.charAt(i - 1), p.charAt(j - 2)));
          }
        }
      }
      return dp[s.length()][p.length()];
    }

    public boolean isEquals(char s, char p) {
      return p == s ? true : (p == '.' ? true : false);
    }
  }
}
